BZOJ3673 可持久化并查集 by zky <可持久化数组>

Problem

可持久化并查集 by zky

Description

个集合个操作
操作：
合并所在集合
回到第次操作之后的状态(查询算作操作)
询问是否属于同一集合，是则输出否则输出

Input

第一行两个整数
以后行，每行三个或两个整数或，意义如上所述

Ouput

对于每个操作，输出

Sample Input

Sample Output

1
2
3

1
0
1

Hint

标签：主席树 可持久化数组

Solution

本题的做法其实和并查集没太大关联。
如果是撤销，那可以用不加路径压缩的并查集完成，但是如果回到某时间，则不太好写。
这时，我们发现并查集这个东西构造其实很简单，只需要一个数组就行了。所以我们自然可以想到直接用一个二维数组存储每个时间的数组，即用增加的一维表示时间。
但是，、是级别，所以肯定会，这里我们就需要用到主席树，把数组可持久化。这里需要注意我们不能用路径压缩优化，因为我们需要回到前面的状态，为了让它跑得更快，我们可以用按秩合并优化。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 20000
using namespace std;
int n, m, cnt, now, root[MAX_N*10+5];
struct node {int fa, dep, ls, rs;} tr[MAX_N*100+5];
void build(int v, int l, int r) {
    if (l == r) {tr[v].fa = l;	return;}
    int mid = l+r>>1;
    tr[v].ls = ++cnt, tr[v].rs = ++cnt;
    build(tr[v].ls, l, mid);
    build(tr[v].rs, mid+1, r);
}
void modifyfa(int v, int o, int s, int t, int pos, int x) {
    tr[v] = tr[o];
    if (s == t)	{tr[v].fa = x;	return;}
    int mid = s+t>>1;
    if (pos <= mid)	modifyfa(tr[v].ls = ++cnt, tr[o].ls, s, mid, pos, x);
    else	modifyfa(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, pos, x);
}
void modifydep(int v, int s, int t, int pos) {
    if (s == t)	{tr[v].dep++;	return;}
    int mid = s+t>>1;
    if (pos <= mid)	modifydep(tr[v].ls, s, mid, pos);
    else	modifydep(tr[v].rs, mid+1, t, pos);
}
int find(int v, int s, int t, int pos) {
    if (s == t)	return v;
    int mid = s+t>>1;
    if (pos <= mid)	return find(tr[v].ls, s, mid, pos);
    else	return find(tr[v].rs, mid+1, t, pos);
}
int getf(int r, int x) {
    int pos = find(r, 1, n, x);
    if (tr[pos].fa != x)	return getf(r, tr[pos].fa);
    return pos;
}
int main() {
    scanf("%d%d", &n, &m);
    cnt = 0, root[0] = ++cnt;
    build(root[0], 1, n);
    for (int now = 1; now <= m; now++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            root[now] = root[now-1];
            int a, b;
            scanf("%d%d", &a, &b);
            int posa = getf(root[now], a), posb = getf(root[now], b);
            if (tr[posa].fa == tr[posb].fa)	continue;
            if (tr[posa].dep > tr[posb].dep)	swap(posa, posb);
            root[now] = ++cnt;
            modifyfa(root[now], root[now-1], 1, n, tr[posa].fa, tr[posb].fa);
            if (tr[posa].dep == tr[posb].dep)	modifydep(root[now], 1, n, tr[posb].fa);
        }
        if (opt == 2) {
            int k;
            scanf("%d", &k);
            root[now] = root[k];
        }
        if (opt == 3) {
            root[now] = root[now-1];
            int a, b;
            scanf("%d%d", &a, &b);
            if (tr[getf(root[now], a)].fa == tr[getf(root[now], b)].fa)	printf("1\n");
            else	printf("0\n");
        }
    }
    return 0;
}